翻訳と辞書 Words near each other ・ Distributed intelligence ・ Distributed Interactive Simulation ・ Distributed key generation ・ Distributed knowledge ・ Distributed lag ・ Distributed language ・ Distributed Language Translation ・ Distributed leadership ・ Distributed learning ・ Distributed library ・ Distributed lock manager ・ Distributed management ・ Distributed Management Task Force ・ Distributed manufacturing ・ Distributed memory ・ Distributed minimum spanning tree ・ Distributed mode loudspeaker ・ Distributed morphology ・ Distributed multi-agent reasoning system ・ Distributed Multi-Link Trunking ・ Distributed multipole analysis ・ Distributed networking ・ Distributed object ・ Distributed object communication ・ Distributed object middleware ・ Distributed Objects Everywhere ・ Distributed Oceanographic Data Systems ・ Distributed operating system ・ Distributed operations ・ Distributed Overlay Virtual Ethernet Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Distributed minimum spanning tree ： ウィキペディア英語版 Distributed minimum spanning tree The distributed minimum spanning tree (MST) problem involves the construction of a minimum spanning tree by a distributed algorithm, in a network where nodes communicate by message passing. It is radically different from the classical sequential problem, although the most basic approach resembles Borůvka's algorithm. One important application of this problem is to find a tree that can be used for broadcasting. In particular, if the cost for a message to pass through an edge in a graph is significant, a MST can minimize the total cost for a source process to communicate with all the other processes in the network. The problem was first suggested and solved in $O(V\; \backslash log\; V)$ time in 1983 by Gallager ''et al.'',〔 where $V$ is the number of vertices in the graph. Later, the solution was improved to $O(V)$〔Baruch Awerbuch. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” ''Proceedings of the 19th ACM Symposium on Theory of Computing (STOC)'', New York City, New York, May 1987. 〕 and finally〔Juan Garay, Shay Kutten and David Peleg, “A Sub-Linear Time Distributed Algorithm for Minimum-Weight Spanning Trees (Extended Abstract),” ''Proceedings of the IEEE Symposium on Foundations of Computer Science'' (FOCS), 1993.〕〔Shay Kutten and David Peleg, “Fast Distributed Construction of Smallk-Dominating Sets and Applications,” ''Journal of Algorithms'', Volume 28, Issue 1, July 1998, Pages 40-66.〕 $O(\backslash sqrt\; V\; \backslash log^$ * V + D) where ''D'' is the network, or graph diameter. A lower bound on the time complexity of the solution has been eventually shown to be〔David Peleg and Vitaly Rubinovich “A near tight lower bound on the time complexity of Distributed Minimum Spanning Tree Construction,“ ''SIAM Journal on Computing'', 2000, and ''IEEE Symposium on Foundations of Computer Science (FOCS)'', 1999.〕 $\backslash Omega\backslash left(\}\backslash right).$ == Overview == The input graph $G(V,E)$ is considered to be a network, where vertices $V$ are independent computing nodes and edges $E$ are communication links. Links are weighted as in the classical problem. At the beginning of the algorithm, nodes know only the weights of the links which are connected to them. (It is possible to consider models in which they know more, for example their neighbors' links.) As the output of the algorithm, every node knows which of its links belong to the Minimum Spanning Tree and which do not. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Distributed minimum spanning tree」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.